#include<stdio.h>
#include<malloc.h>

void show_shell_sort(int* a,int n){
    int i,j,k,l,d,cur;
    d = n;
    while(d>1){
        d /= 2;
        for(k=0;k<d;k++){ // d组，做d次插入排序，甚至可以直接套上面的代码
            for(i=k;i<n;i+=d){
                cur = a[i];
                for(j=k;j<i;j+=d)if( cur<a[j] )break;
                if(j<i)for(l=i;l>j;l-=d)a[l]=a[l-d];
                a[j] = cur;
            }
        }
    }
}

int main(int argc,char** argv){
    int NUM_SIZE = 0; int i;
    printf("Enter Element Count: ");
    scanf("%d",&NUM_SIZE);
    printf("Enter Elements seperated with white spaces:\n");
    int* shell = malloc(sizeof(int)*NUM_SIZE);
    for(i=0;i<NUM_SIZE;i++)scanf("%d",shell+i);
    show_shell_sort(shell,NUM_SIZE);
    for(i=0;i<NUM_SIZE;i++)printf("%d ",shell[i]);putchar('\n');
    return 0;
}
